0648. 单词替换【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希集合

1. 📝 题目描述

• leetcode

在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着 继承词 "ful"，可以形成新的单词 "helpful"。

现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用 词根 替换掉。如果 衍生词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。

你需要输出替换之后的句子。

---

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

---

提示：

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写字母组成。
• 1 <= sentence.length <= 10^6
• sentence 仅由小写字母和空格组成。
• sentence 中单词的总量在范围 [1, 1000] 内。
• sentence 中每个单词的长度在范围 [1, 1000] 内。
• sentence 中单词之间由一个空格隔开。
• sentence 没有前导或尾随空格。

2. 🎯 s.1 - 哈希集合

c

// 简化实现，使用排序 + 前缀匹配
int cmpStr(const void* a, const void* b) { return strcmp(*(char**)a, *(char**)b); }

char* replaceWords(char** dictionary, int dictionarySize, char* sentence) {
    qsort(dictionary, dictionarySize, sizeof(char*), cmpStr);
    char* res = (char*)malloc(strlen(sentence) + 1);
    int pos = 0;
    char* token = strtok(sentence, " ");
    int first = 1;
    while (token) {
        if (!first) res[pos++] = ' ';
        first = 0;
        char* best = token;
        for (int i = 0; i < dictionarySize; i++) {
            int len = strlen(dictionary[i]);
            if (strncmp(token, dictionary[i], len) == 0) {
                if (strlen(best) == strlen(token) || len < strlen(best))
                    best = dictionary[i];
            }
        }
        strcpy(res + pos, best);
        pos += strlen(best);
        token = strtok(NULL, " ");
    }
    res[pos] = '\0';
    return res;
}

js

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function (dictionary, sentence) {
  const set = new Set(dictionary)
  return sentence
    .split(' ')
    .map((word) => {
      for (let i = 1; i <= word.length; i++) {
        const prefix = word.substring(0, i)
        if (set.has(prefix)) return prefix
      }
      return word
    })
    .join(' ')
}

py

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root_set = set(dictionary)
        def replace(word):
            for i in range(1, len(word) + 1):
                if word[:i] in root_set:
                    return word[:i]
            return word
        return ' '.join(replace(w) for w in sentence.split())

• 时间复杂度：$O(d+s\times l)$，其中 d 是词根总长度，s 是句子单词数，l 是单词平均长度
• 空间复杂度：$O(d)$

算法思路：

• 将所有词根存入哈希集合
• 对句子中每个单词，从短到长枚举前缀，找到第一个匹配的词根即替换